package main

import (
	"errors"
	"fmt"
)

// Queue 队列结构体
type Queue struct {
	items []interface{}
}

// NewQueue 创建新队列
func NewQueue() *Queue {
	return &Queue{
		items: make([]interface{}, 0),
	}
}

// Enqueue 入队
func (q *Queue) Enqueue(item interface{}) {
	q.items = append(q.items, item)
	fmt.Printf("入队: %v\n", item)
}

// Dequeue 出队
func (q *Queue) Dequeue() (interface{}, error) {
	if q.IsEmpty() {
		return nil, errors.New("队列为空")
	}
	item := q.items[0]
	q.items = q.items[1:]
	fmt.Printf("出队: %v\n", item)
	return item, nil
}

// Front 查看队头元素
func (q *Queue) Front() (interface{}, error) {
	if q.IsEmpty() {
		return nil, errors.New("队列为空")
	}
	return q.items[0], nil
}

// IsEmpty 判断队列是否为空
func (q *Queue) IsEmpty() bool {
	return len(q.items) == 0
}

// Size 获取队列的大小
func (q *Queue) Size() int {
	return len(q.items)
}

// Clear 清空队列
func (q *Queue) Clear() {
	q.items = q.items[:0]
	fmt.Println("队列已清空")
}

// Print 打印队列内容
func (q *Queue) Print() {
	fmt.Printf("队列内容: %v\n", q.items)
}

// CircularQueue 循环队列结构体
type CircularQueue struct {
	queue    []interface{}
	capacity int
	front    int
	rear     int
	size     int
}

// NewCircularQueue 创建新循环队列
func NewCircularQueue(capacity int) *CircularQueue {
	return &CircularQueue{
		queue:    make([]interface{}, capacity),
		capacity: capacity,
		front:    0,
		rear:     0,
		size:     0,
	}
}

// Enqueue 入队
func (cq *CircularQueue) Enqueue(item interface{}) error {
	if cq.IsFull() {
		return errors.New("队列已满")
	}
	cq.queue[cq.rear] = item
	cq.rear = (cq.rear + 1) % cq.capacity
	cq.size++
	fmt.Printf("入队: %v\n", item)
	return nil
}

// Dequeue 出队
func (cq *CircularQueue) Dequeue() (interface{}, error) {
	if cq.IsEmpty() {
		return nil, errors.New("队列为空")
	}
	item := cq.queue[cq.front]
	cq.queue[cq.front] = nil // 清空元素
	cq.front = (cq.front + 1) % cq.capacity
	cq.size--
	fmt.Printf("出队: %v\n", item)
	return item, nil
}

// IsEmpty 判断队列是否为空
func (cq *CircularQueue) IsEmpty() bool {
	return cq.size == 0
}

// IsFull 判断队列是否已满
func (cq *CircularQueue) IsFull() bool {
	return cq.size == cq.capacity
}

// GetSize 获取队列大小
func (cq *CircularQueue) GetSize() int {
	return cq.size
}

// Print 打印队列内容
func (cq *CircularQueue) Print() {
	fmt.Print("循环队列内容: ")
	for i := 0; i < cq.size; i++ {
		idx := (cq.front + i) % cq.capacity
		fmt.Printf("%v ", cq.queue[idx])
	}
	fmt.Println()
}

// TaskScheduler 任务调度器
type TaskScheduler struct {
	taskQueue *Queue
}

// NewTaskScheduler 创建新任务调度器
func NewTaskScheduler() *TaskScheduler {
	return &TaskScheduler{
		taskQueue: NewQueue(),
	}
}

// SubmitTask 提交任务
func (ts *TaskScheduler) SubmitTask(task string) {
	ts.taskQueue.Enqueue(task)
	fmt.Printf("任务已提交: %s\n", task)
}

// ExecuteNextTask 执行下一个任务
func (ts *TaskScheduler) ExecuteNextTask() (string, error) {
	if !ts.taskQueue.IsEmpty() {
		task, err := ts.taskQueue.Dequeue()
		if err != nil {
			return "", err
		}
		fmt.Printf("正在执行: %v\n", task)
		return task.(string), nil
	} else {
		fmt.Println("没有待执行的任务")
		return "", errors.New("没有待执行的任务")
	}
}

// GetTaskCount 获取任务数量
func (ts *TaskScheduler) GetTaskCount() int {
	return ts.taskQueue.Size()
}

// BFS 广度优先搜索
func BFS(graph map[string][]string, start string) []string {
	var result []string
	visited := make(map[string]bool)
	queue := NewQueue()
	
	queue.Enqueue(start)
	visited[start] = true
	
	for !queue.IsEmpty() {
		vertex, _ := queue.Dequeue()
		vertexStr := vertex.(string)
		result = append(result, vertexStr)
		
		neighbors := graph[vertexStr]
		for _, neighbor := range neighbors {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue.Enqueue(neighbor)
			}
		}
	}
	
	return result
}

// testBasicOperations 测试基本操作
func testBasicOperations() {
	fmt.Println("==================================================")
	fmt.Println("测试队列的基本操作")
	fmt.Println("==================================================")
	
	queue := NewQueue()
	
	// 测试空队列
	fmt.Printf("队列是否为空: %t\n", queue.IsEmpty())
	fmt.Printf("队列的大小: %d\n", queue.Size())
	
	// 入队操作
	fmt.Println("\n--- 入队操作 ---")
	queue.Enqueue(1)
	queue.Enqueue(2)
	queue.Enqueue(3)
	queue.Enqueue("hello")
	queue.Enqueue([]int{4, 5, 6})
	
	queue.Print()
	fmt.Printf("队列的大小: %d\n", queue.Size())
	
	if front, err := queue.Front(); err == nil {
		fmt.Printf("队头元素: %v\n", front)
	}
	
	// 出队操作
	fmt.Println("\n--- 出队操作 ---")
	for !queue.IsEmpty() {
		queue.Dequeue()
		queue.Print()
	}
	
	fmt.Printf("队列是否为空: %t\n", queue.IsEmpty())
}

// testCircularQueue 测试循环队列
func testCircularQueue() {
	fmt.Println("\n==================================================")
	fmt.Println("测试循环队列")
	fmt.Println("==================================================")
	
	cq := NewCircularQueue(3)
	
	// 入队操作
	cq.Enqueue(1)
	cq.Enqueue(2)
	cq.Enqueue(3)
	cq.Print()
	
	// 出队一个元素
	cq.Dequeue()
	cq.Print()
	
	// 继续入队
	cq.Enqueue(4)
	cq.Print()
	
	// 全部出队
	for !cq.IsEmpty() {
		cq.Dequeue()
		cq.Print()
	}
}

// testTaskScheduler 测试任务调度器
func testTaskScheduler() {
	fmt.Println("\n==================================================")
	fmt.Println("测试任务调度器")
	fmt.Println("==================================================")
	
	scheduler := NewTaskScheduler()
	scheduler.SubmitTask("任务A")
	scheduler.SubmitTask("任务B")
	scheduler.SubmitTask("任务C")
	
	fmt.Printf("待执行任务数: %d\n", scheduler.GetTaskCount())
	
	scheduler.ExecuteNextTask() // 执行任务A
	scheduler.ExecuteNextTask() // 执行任务B
	scheduler.ExecuteNextTask() // 执行任务C
	scheduler.ExecuteNextTask() // 没有任务
}

// testBFS 测试广度优先搜索
func testBFS() {
	fmt.Println("\n==================================================")
	fmt.Println("测试广度优先搜索")
	fmt.Println("==================================================")
	
	// 示例图
	graph := map[string][]string{
		"A": {"B", "C"},
		"B": {"A", "D", "E"},
		"C": {"A", "F"},
		"D": {"B"},
		"E": {"B", "F"},
		"F": {"C", "E"},
	}
	
	result := BFS(graph, "A")
	fmt.Printf("BFS遍历结果: %v\n", result)
}

func main() {
	fmt.Println("队列（Queue）数据结构演示程序")
	fmt.Println("==================================================")
	
	// 运行所有测试
	testBasicOperations()
	testCircularQueue()
	testTaskScheduler()
	testBFS()
	
	fmt.Println("\n==================================================")
	fmt.Println("所有测试完成！")
	fmt.Println("==================================================")
}
